#include "hash_map.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// 哈希函数 (FNV-1a)
static uint32_t hash_function(const char *key) {
    uint32_t hash = 2166136261u;
    while (*key) {
        hash ^= (uint8_t)*key++;
        hash *= 16777619;
    }
    return hash;
}

// 创建新的 Map
HashMap *map_create(size_t capacity) {
    HashMap *map = malloc(sizeof(HashMap));
    if (!map) return NULL;
    
    map->buckets = calloc(capacity, sizeof(MapEntry*));
    if (!map->buckets) {
        free(map);
        return NULL;
    }
    
    map->capacity = capacity;
    map->size = 0;
    return map;
}

// 重新哈希所有元素到新桶中
static void rehash(HashMap *map, MapEntry **new_buckets, size_t new_capacity) {
    for (size_t i = 0; i < map->capacity; i++) {
        MapEntry *entry = map->buckets[i];
        while (entry) {
            MapEntry *next = entry->next;
            
            // 计算在新桶中的位置
            uint32_t new_index = hash_function(entry->key) % new_capacity;
            
            // 插入到新桶的链表头部
            entry->next = new_buckets[new_index];
            new_buckets[new_index] = entry;
            
            entry = next;
        }
    }
}

// 动态扩容函数
static int resize(HashMap *map) {
    // 计算新容量（通常是原来的2倍）
    size_t new_capacity = map->capacity * 2;
    
    // 分配新桶数组
    MapEntry **new_buckets = calloc(new_capacity, sizeof(MapEntry*));
    if (!new_buckets) {
        return 0; // 扩容失败
    }
    
    // 重新哈希所有元素
    rehash(map, new_buckets, new_capacity);
    
    // 释放旧桶数组
    free(map->buckets);
    
    // 更新map结构
    map->buckets = new_buckets;
    map->capacity = new_capacity;
    
    return 1; // 扩容成功
}

// 添加键值对（带自动扩容和内存管理）
int map_put(HashMap *map, const char *key, void *value, void (*value_free)(void*)) {
    if (!map || !key) return 0;
    
    // 检查是否需要扩容
    double load_factor = (double)map->size / map->capacity;
    if (load_factor > LOAD_FACTOR_THRESHOLD) {
        if (!resize(map)) {
            printf("⚠️ 扩容失败，继续使用当前容量\n");
        } else {
            printf("✅ 扩容成功，新容量: %zu\n", map->capacity);
        }
    }
    
    uint32_t index = hash_function(key) % map->capacity;
    
    // 检查键是否已存在
    MapEntry *entry = map->buckets[index];
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            // 释放旧值内存（如果存在释放函数）
            if (entry->value_free && entry->value) {
                entry->value_free(entry->value);
            }
            
            // 更新值和释放函数
            entry->value = value;
            entry->value_free = value_free;
            return 1;
        }
        entry = entry->next;
    }
    
    // 创建新条目
    MapEntry *new_entry = malloc(sizeof(MapEntry));
    if (!new_entry) return 0;
    
    new_entry->key = strdup(key);
    if (!new_entry->key) {
        free(new_entry);
        return 0;
    }
    
    new_entry->value = value;
    new_entry->value_free = value_free;
    new_entry->next = map->buckets[index];
    map->buckets[index] = new_entry;
    map->size++;
    
    return 1;
}

// 获取值
void *map_get(HashMap *map, const char *key) {
    if (!map || !key) return NULL;
    
    uint32_t index = hash_function(key) % map->capacity;
    MapEntry *entry = map->buckets[index];
    
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    
    return NULL;
}

// 删除键值对（带内存释放）
int map_remove(HashMap *map, const char *key) {
    if (!map || !key) return 0;
    
    uint32_t index = hash_function(key) % map->capacity;
    MapEntry *entry = map->buckets[index];
    MapEntry *prev = NULL;
    
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            if (prev) {
                prev->next = entry->next;
            } else {
                map->buckets[index] = entry->next;
            }
            
            // 释放键内存
            free(entry->key);
            
            // 释放值内存（如果存在释放函数）
            if (entry->value_free && entry->value) {
                entry->value_free(entry->value);
            }
            
            free(entry);
            map->size--;
            return 1;
        }
        
        prev = entry;
        entry = entry->next;
    }
    
    return 0;
}

// 检查键是否存在
int map_contains(HashMap *map, const char *key) {
    return map_get(map, key) != NULL;
}

// 获取Map大小
size_t map_size(HashMap *map) {
    return map ? map->size : 0;
}

// 获取Map容量
size_t map_capacity(HashMap *map) {
    return map ? map->capacity : 0;
}

// 计算当前负载因子
double map_load_factor(HashMap *map) {
    if (!map || map->capacity == 0) return 0.0;
    return (double)map->size / map->capacity;
}

// 销毁Map（带完整内存释放）
void map_destroy(HashMap *map) {
    if (!map) return;
    
    for (size_t i = 0; i < map->capacity; i++) {
        MapEntry *entry = map->buckets[i];
        while (entry) {
            MapEntry *next = entry->next;
            
            // 释放键内存
            free(entry->key);
            
            // 释放值内存（如果存在释放函数）
            if (entry->value_free && entry->value) {
                entry->value_free(entry->value);
            }
            
            free(entry);
            entry = next;
        }
    }
    
    free(map->buckets);
    free(map);
}

// 内存释放函数示例
void int_free(void *ptr) {
    if (ptr) free(ptr);
}

void str_free(void *ptr) {
    if (ptr) free(ptr);
}

// 打印Map状态
void map_print_status(HashMap *map) {
    if (!map) return;
    
    printf("容量: %zu, 大小: %zu, 负载因子: %.2f\n", 
           map->capacity, map->size, map_load_factor(map));
}
// 测试函数
int test() {
    printf("🚀 C语言Map实现测试（完整整合版）\n");
    
    // 创建Map
    HashMap *map = map_create(INITIAL_CAPACITY);
    if (!map) {
        printf("❌ 创建Map失败\n");
        return 1;
    }
    
    printf("初始状态: ");
    map_print_status(map);
    
    // 测试添加元素
    printf("\n测试添加元素...\n");
    int *a = malloc(sizeof(int));
    *a = 100;
    
    float *b = malloc(sizeof(float));
    *b = 3.14f;
    
    char *c = strdup("Hello, Map!");
    
    map_put(map, "int_value", a, int_free);
    map_put(map, "float_value", b, int_free);
    map_put(map, "string_value", c, str_free);
    
    printf("✅ 添加3个元素\n");
    map_print_status(map);
    
    // 测试获取元素
    printf("\n测试获取元素...\n");
    int *int_ptr = map_get(map, "int_value");
    if (int_ptr && *int_ptr == 100) {
        printf("✅ int_value: %d\n", *int_ptr);
    } else {
        printf("❌ int_value获取失败\n");
    }
    
    float *float_ptr = map_get(map, "float_value");
    if (float_ptr && *float_ptr == 3.14f) {
        printf("✅ float_value: %.2f\n", *float_ptr);
    } else {
        printf("❌ float_value获取失败\n");
    }
    
    char *str_ptr = map_get(map, "string_value");
    if (str_ptr && strcmp(str_ptr, "Hello, Map!") == 0) {
        printf("✅ string_value: %s\n", str_ptr);
    } else {
        printf("❌ string_value获取失败\n");
    }
    
    // 测试更新元素（内存安全）
    printf("\n测试更新元素...\n");
    int *new_a = malloc(sizeof(int));
    *new_a = 200;
    map_put(map, "int_value", new_a, int_free);
    
    int_ptr = map_get(map, "int_value");
    if (int_ptr && *int_ptr == 200) {
        printf("✅ int_value更新成功: %d\n", *int_ptr);
    } else {
        printf("❌ int_value更新失败\n");
    }
    
    // 测试删除元素
    printf("\n测试删除元素...\n");
    map_remove(map, "float_value");
    if (!map_contains(map, "float_value")) {
        printf("✅ float_value删除成功\n");
    } else {
        printf("❌ float_value删除失败\n");
    }
    
    // 测试动态扩容
    printf("\n测试动态扩容...\n");
    for (int i = 0; i < 20; i++) {
        char key[20];
        sprintf(key, "key_%d", i);
        
        int *value = malloc(sizeof(int));
        *value = i * 10;
        
        map_put(map, key, value, int_free);
        
        if (i == 11) { // 预期在第12个元素时触发扩容
            printf("触发扩容: ");
            map_print_status(map);
        }
    }
    
    // 验证扩容后数据完整性
    printf("\n验证扩容后数据完整性...\n");
    for (int i = 0; i < 20; i++) {
        char key[20];
        sprintf(key, "key_%d", i);
        
        int *value = map_get(map, key);
        if (value && *value == i * 10) {
            printf("✅ %s: %d\n", key, *value);
        } else {
            printf("❌ %s 验证失败\n", key);
        }
    }
    
    printf("最终状态: ");
    map_print_status(map);
    
    // 清理
    map_destroy(map);
    printf("✅ Map销毁完成\n");
    
    return 0;
}

